package 二叉树;


import Utils.TreeNode;

import java.util.HashMap;

/**
 * @author TTDB
 * @create 2025/9/18
 */
public class buildTree {
 //从前序和中序遍历构造二叉树
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            valToIndex.put(inorder[i], i);
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] order,int inStart,int inEnd){
        if(preStart> preEnd) return null;
        //这里可以这样也可以直接用HashMap获取这个index,获取头节点在中序遍历中的索引，
        int rootVal = preorder[preStart];
        int index = valToIndex.get(rootVal);
        //关键确定长度后区分
        int leftSize = index - inStart;
        // 然后根据这个索引就区分左右子树的范围
        //前序遍历的就需要获取到左子树的长度，然后根据这个长度就可以获取到左子树的范围
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder,preStart + 1, preStart+leftSize, order, inStart, index -1);
        root.right = build(preorder, preStart + leftSize + 1,preEnd, order, index+1, inEnd);
        return root;
    }
}